package array;
/**
 * 4.已知有个升序的数组，要求插入一个元素，该数组顺序依然是升序，比如：
 * [10, 12,45,90]，添加23后,数组为[10, 12,23,45,90]
 */
public class 插入到有序数组中 {
    public static void main(String[] args) {
        /*
        思路：
        顺序遍历原来的数组，把要插入的值和数组的值比较，如果发现
        insertNum<=arr[i],说明i就是要插入的下标
        返回要插入的下标
        重新遍历新数组
        没轮到下标的时候，就原数组的数赋值到新的数组，轮到下标那就是下标。
        边界条件判断，如果要插入的值并不满足insertNum<=arr[i]，说明要插入的值再最右边
        代码一样不用变
        垃圾考虑，扩容后的数组就是我们要的，这个时候直接把newArr地址赋值给arr，arr就消失了
        会被当成垃圾清理掉
         */
        int[] arr = {10, 12,45,90};
        int[] newArr = new int[arr.length+1];
        int insertNum = 23;
        int index = -1;//下标
        for (int i = 0; i < arr.length; i++) {
            if(insertNum <= arr[i]){
                index = i;
                break;
            }
        }
        //没进入if，插入到最右边
        if(index==-1){
            index = arr.length;
        }
        for (int i = 0 ,j = 0; i < newArr.length; i++) {
            if(i != index){
                // 数组越界问题
                // j 的最大值：
                //由于 j 只有在 i 不等于 index 时才会增加，因此 j 的最大值是 arr.length - 1。
                //即使 i 达到 newArr.length - 1，j 也不会超过 arr.length - 1，因此不会发生数组越界。
                newArr[i] = arr[j];
                j++;
            }else {
                newArr[i] = insertNum;
            }
        }
        //垃圾清理
        arr = newArr;
        for (int i = 0; i < newArr.length; i++) {
            System.out.print(newArr[i]+" ");
        }
    }
}
